/FONT#0=BASL30/FONT#1=BASI30/FONT#2=SUB/FONT#3=NGR40/FONT#4=BDB30
␈↓␈↓↓␈↓α␈↓β␈↓∧␈↓β␈↓ ∧"COMPUTER SCIENCE DEPARTMENT
␈↓ ¬	STANFORD UNIVERSITY

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓ ↓⊂CS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1973
␈↓ ¬iFINAL EXAM
␈↓␈↓ ¬?Open Books and Notes

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓ ↓H1.␈α␈↓↓alt␈↓[␈↓↓u,␈αm,␈αn␈↓]␈αtakes␈αevery␈α␈↓↓n␈↓th␈αelement␈αof␈αthe␈αlist␈α␈↓↓u␈↓␈αstarting␈αwith␈αthe␈α␈↓↓n␈↓th.␈αWrite␈αa␈α
recursive␈α
defintion
␈↓ ↓Hof␈α
␈↓↓alt␈↓[␈↓↓u,␈α
m,␈α
n␈↓].

␈↓ ↓H2.␈α
␈↓↓odds␈α
u␈↓␈α
is␈α
a␈α
list␈α
of␈α
the␈α
elements␈α
of␈α
the␈α
list␈α
␈↓↓u␈↓␈α
that␈α
occur␈α
in␈α
␈↓↓u␈↓␈α
an␈α
odd␈α
number␈αof␈αtimes.␈αWrite␈αthe
␈↓ ↓Hfastest␈α∂definition␈α∂of␈α∂␈↓↓odds␈α∂u␈↓␈α∂that␈α∂you␈α∂can.␈α∂Give␈α∂several␈α∂if␈α∂you␈α∂like,␈α∂but␈α∂be␈α∞sure␈α∞to␈α∞have␈α∞one␈α∞that
␈↓ ↓Hworks.

␈↓ ↓H3.␈α
Let␈α
a␈α
graph␈α
␈↓↓g␈↓␈α
be␈α
described␈α
as␈α
in␈α
chapter␈α
1␈α
of␈α
the␈αnotes␈αand␈αsuppose␈αthat␈αwhenever␈αthere␈αis␈αan
␈↓ ↓Hedge␈α∂from␈α∂␈↓↓x␈↓␈α∂to␈α∞␈↓↓y␈↓␈α∞there␈α∞is␈α∞also␈α∞an␈α∞edge␈α∞from␈α∞␈↓↓y␈↓␈α∞to␈α∞␈↓↓x␈↓.␈α∞A␈α∞component␈α∞of␈α∞the␈α∞graph␈α∞is␈α∞a␈α∞collection␈α∞of
␈↓ ↓Hvertices␈αwhich␈αare␈αall␈αconnected␈αto␈αeach␈αother␈αby␈αedge␈αpaths␈αbut␈αnot␈αconnected␈αto␈α
any␈α
other␈α
vertices.
␈↓ ↓HWrite␈α
a␈α
function␈α
to␈α
determine␈α
the␈α
number␈α
of␈α
components.

␈↓ ↓H4.␈α
The␈α
␈↓↓n␈↓th␈α
Fibonacci␈α
number␈α
is␈α
defined␈α
by␈α
the␈α
equations

␈↓ ↓H
␈↓ α_F␈↓α0␈↓ = 1
␈↓ ↓H
␈↓ α_F␈↓α1␈↓ = 1
␈↓ ↓H
␈↓ α_F␈↓αn+2␈↓ = F␈↓αn+1␈↓ + F␈↓αn␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HThus␈α
we␈α
have␈α
F␈↓α2␈↓␈α
=␈α
2,␈α
F␈↓α3␈↓␈α
=␈α
3,␈α
F␈↓α4␈↓␈α
=␈α
5,␈α
F␈↓α5␈↓␈α
=␈α
8,␈α
etc.

␈↓ ↓HThis␈α
definition␈α
translates␈α
into␈α
LISP␈α
as

␈↓ ↓H
␈↓ α_F␈↓αn␈↓ ← ␈↓∧if␈↓↓ n␈↓ = 0 ␈↓∧∨ ␈↓↓n␈↓ = 1 ␈↓∧then␈↓ 1 ␈↓∧else␈↓ F␈↓αn-2␈↓ + F␈↓αn-1␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ α_What␈α
bad␈α
thing␈α
will␈α
happen␈α
if␈α
we␈α
try␈α
to␈α
compute␈α
F␈↓α100␈↓␈α
using␈α
this␈α
definition?
␈↓ α_Write␈α
a␈α
new␈α
LISP␈α
definition␈α
of␈α
F␈↓αn␈↓␈α
not␈α
suffering␈α
from␈α
this␈α
problem.

␈↓ ↓H5.␈α
Do␈α
␈↓∧one␈↓␈α
of␈α
a␈α
and␈α
b.

␈↓ α_a.␈α⊂Compare␈α⊂the␈α⊂versions␈α⊂of␈α⊂COMPANDOR␈α∂in␈α∂LCOMO␈α∂and␈α∂LCOM4.␈α∂Give␈α∂the␈α∂simplest
␈↓ ↓Hexample␈α∩you␈α∩can␈α∩of␈α⊃an␈α⊃expression␈α⊃for␈α⊃which␈α⊃LCOM4␈α⊃generates␈α⊃better␈α⊃code␈α⊃showing␈α⊃the␈α⊃code
␈↓ ↓Hgenerated␈α
by␈α
each.

␈↓ α_b.␈α∀The␈α∀definition␈α∀of␈α∀␈↓↓ter␈↓␈α∀in␈α∀TICTAC2.LSP␈α∀is␈α∀not␈α∀very␈α∀elegant␈α∀and␈α∪not␈α∪very␈α∪efficient.
␈↓ ↓HEssentially␈α∞the␈α
same␈α
thing␈α
is␈α
done␈α
better␈α
in␈α
the␈α
definition␈α
of␈α
␈↓↓win␈↓.␈α
Revise␈α
␈↓↓ter␈↓␈α
accordingly.␈α
Likewise
␈↓ ↓Hrevise␈α
␈↓↓imval␈↓.